Inteligencia Artificial

1 Contenido de la clase

De agentes solos a adversarios: tipos de juegos [00:00-04:00]

En las clases anteriores los agentes estaban solos en su ambiente; después vimos una población de individuos que resuelven un problema; ahora en el ambiente hay adversarios. Los juegos se clasifican según varios ejes: determinista o estocástico (con azar: dados, cartas), número de jugadores, suma cero (la ganancia de uno es la pérdida del otro) e información perfecta (se ve todo el estado, como en el ajedrez). El audio menciona juegos de cartas con azar que admiten varios jugadores (hasta 9 o 10), aunque los nombres transcritos no son confiables [parte no entendida]. Queremos algoritmos que calculen la estrategia para movernos en cada estado.

El estado del arte en juegos [03:53-06:12]

Damas inglesas: el primer programa que jugaba es de 1952 (Strachey; la conferencia dijo "1950", impreciso); en 1992 el programa Chinook retó al campeón Marion Tinsley y en 1994 fue por primera vez campeón mundial (tras el retiro de Tinsley); desde 2007 el juego quedó resuelto (es tablas con juego perfecto). Ajedrez: en 1997 Deep Blue derrotó al campeón mundial (Kasparov). Go: en 2016 AlphaGo venció al profesional Lee Sedol; el Go tiene un espacio de búsqueda enorme. AlphaZero (2017): a diferencia de AlphaGo (que aprendió de partidas humanas), aprende jugando contra sí mismo con solo las reglas, y venció a Stockfish [Conferencia IA 7; parte no entendida en tramos].

Definición formal de un juego [06:42-08:45]

Un juego se formaliza con estados S (inicia en s0), jugadores P = {1, …, N}, acciones A (dependen de cada jugador y del estado), función de transición S × A → S, prueba de meta S → {verdadero, falso} y utilidad terminal S × P → R (los puntos de cada jugador al final). La solución para un jugador es una estrategia S → A: qué acción tomar en cada estado [06:42-08:45].

Suma cero y juegos en general [09:29-09:58]

En los juegos de suma cero los agentes tienen utilidades opuestas: alguien gana y alguien pierde en la misma cantidad; es pura competencia. En los juegos en general los agentes tienen utilidades independientes: existe cooperación, indiferencia, competencia y otras posibilidades, y eso puede cambiar con el tiempo [09:29-09:58].

Búsqueda con adversarios: el valor de un estado [20:00-22:02]

No basta decidir de forma independiente qué haré: hay que pensar mis opciones, las de mi oponente y recursivamente ("¿qué hará mi oponente?", "¿qué pensará mi oponente que haré yo?", "¿qué pensará que pensaré que hará él?", …). El valor de un estado es el mejor resultado (utilidad) que se puede obtener desde ese estado. En estados terminales Vs = x con x conocido; en estados no terminales Vs = max sobre los sucesores s′ de V(s′) [21:12-22:02].

Árboles de juegos con adversarios [22:55-23:23]

No tenemos control del árbol completo: solo podemos seleccionar las decisiones propias; para el resto suponemos que lo peor va a suceder. Se juega por turnos alternados: yo me muevo y luego decide el oponente [22:55-23:23].

El algoritmo minimax [27:13-29:42]

Es el algoritmo clásico usado para juegos como el ajedrez (Deep Blue) y uno de los más importantes de la inteligencia artificial. Se aplica a juegos deterministas de suma cero (gato, ajedrez, damas inglesas): un jugador maximiza su resultado y el otro lo minimiza; el espacio de estados es un árbol, cada jugador tiene su turno y se calcula el valor minimax de cada nodo. Estados terminales: Vs = x; estados bajo control del oponente: Vs = min; estados bajo control del agente: Vs = max. Ejemplo con hojas 8, 2, 5 y 6: min(8,2)=2, min(5,6)=5 y la raíz toma max(2,5)=5 [27:35-28:10]. El pseudocódigo: el jugador max inicia el valor en −∞ y hace v = max(v, valor(sucesor)); el jugador min inicia en +∞ y hace v = min(v, valor(sucesor)); si se llega a un estado terminal se devuelve su valor. En palabras del profesor: "yo voy a hacer el máximo de lo que el otro minimiza" [28:30-29:42].

MAX: v = max(v, valor(sucesor))  ·  MIN: v = min(v, valor(sucesor))  ·  "Yo hago el máximo de lo que el otro minimiza" [27:13-29:42]

Propiedades de minimax y más de dos jugadores [29:42-44:37]

Minimax es completo y óptimo para juegos deterministas de suma cero con información perfecta, pero tener el árbol completo es un problema complicado ("no lo vamos a poder hacer"). Complejidad: tiempo O(b^m) y espacio O(b·m), donde b es el factor de ramificación y m la profundidad. Se puede generalizar a más de 2 jugadores con un despachador que decide a quién le toca el turno (max, min, min2, min3, …), como en dominó o parchís [40:00-44:37; tramos [parte no entendida]].

Podado alfa-beta [61:00-65:05]

Sirve para no recorrer todo el árbol ni calcular los valores que no hacen falta. Alfa es el mejor valor que MAX puede tomar en el recorrido actual; beta es el mejor valor que MIN puede tomar. Si el valor de un nodo es peor que alfa, MAX no lo va a considerar y no exploramos esa región (se poda). Se poda cuando el valor es mayor o igual que beta, y se actualiza alfa = max(alfa, valor) [61:00-64:21].

Si n es peor que α → podar esa región  ·  α = max(α, valor) [61:00-64:21]

Propiedades: el podado no tiene efecto en el valor minimax de la raíz; los valores de los nodos intermedios pueden tener errores; la complejidad de tiempo mejora a O(b^(m/2)) con buen orden, y el orden importa (conviene ordenar los sucesores) [64:22-65:05].

Limitantes en recursos y funciones de evaluación [65:07-66:42]

En juegos realistas no se puede llegar a las hojas. Ideas: 1) buscar solo hasta una profundidad definida; 2) reemplazar las utilidades terminales por una evaluación en nodos no terminales (similar al rol de la heurística en A*); 3) usar búsqueda iterativa para un algoritmo "siempre listo": se hace la búsqueda a 5, 10, 20 niveles… y cuando se acaba el tiempo se reportan las mejores opciones (p. ej. ajedrez viendo "8 movimientos al futuro"). La evaluación siempre es imperfecta: a mayor profundidad de búsqueda menos relevante es la calidad de la evaluación, pero es mucho más caro [65:07-66:15].

La función de evaluación ideal regresaría el valor minimax de la posición; nos conformamos con una noción del valor F: R^n → R^k, en general una combinación lineal F̃(s) = w1·f1(s) + w2·f2(s) + … + wn·fn(s), donde las wi ∈ [0,1] representan la relevancia de cada característica [66:18-66:42]. Ejemplos: en ajedrez, el valor de las piezas (rey, reina), cuántas piezas tienes, el control del centro y los movimientos disponibles; en fútbol, evaluar el estado del partido por su probabilidad de ganar dado el momento del encuentro. Al final el profesor anunció el siguiente tema: Incertidumbre [66:42-67:00].

F̃(s) = w1·f1(s) + w2·f2(s) + … + wn·fn(s), con wi ∈ [0,1] [66:18-66:42]

Complementos y precisiones (el libro va más allá)

• Poda hacia delante (forward pruning): podar ramas que "parecen" malas antes de evaluarlas con un criterio (p. ej. quedarse con los n mejores movimientos). Ahorra mucho, a riesgo de podar un buen movimiento.
• Búsqueda vs. tabla (search vs. lookup): en finales conviene precalcular tablas de posiciones en vez de buscar; el ajedrez tiene tablas de todos los finales con hasta 7 piezas.
• Juegos estocásticos (expectiminimax): si hay azar (dados, cartas) se añaden nodos chance que promedian por probabilidad; es el puente con la clase 8.
• Juegos parcialmente observables: si no se ve todo el estado (Kriegspiel, cartas) no basta minimax: se razona con creencias y probabilidad (se profundiza en incertidumbre).
• Monte Carlo Tree Search (MCTS): en vez de expandir todo el árbol, se simulan partidas aleatorias (rollouts) y se concentra el esfuerzo en las ramas prometedoras (selección–expansión–simulación–retropropagación). Fue clave en AlphaGo/AlphaZero y hoy domina en Go.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

No se indicaron tareas en esta clase.

El inicio de la clase incluyó comentarios y dudas sobre la Tarea 1 [00:00-04:00], aunque el tramo es muy ruidoso [parte no entendida].

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

6 Glosario de términos

• Juego con adversarios: problema de decisión donde hay más de un jugador cuyas utilidades pueden ser opuestas [00:00-04:00].
• Suma cero: juego donde la ganancia de un jugador es la pérdida exacta de otro [09:29-09:58].
• Información perfecta: el agente ve todo el estado del juego (p. ej. ajedrez) [00:00-04:00].
• Estrategia: función que indica qué acción tomar en cada estado (S→A) [06:42-08:45].
• Utilidad terminal: puntos que recibe cada jugador al final del juego (S×P→R) [06:42-08:45].
• Valor de un estado: mejor utilidad que se puede obtener desde ese estado; Vs = max V(s′) en no terminales [20:00-22:02].
• Minimax: algoritmo de búsqueda en árboles de juego donde un jugador maximiza y el otro minimiza; completo y óptimo en deterministas de suma cero con información perfecta [27:13-40:00].
• Factor de ramificación (b) y profundidad (m): parámetros que determinan la complejidad O(b^m) de minimax [29:42-40:00].
• Poda alfa-beta: técnica que deja de explorar ramas que no pueden mejorar el resultado, sin cambiar el valor de la raíz [61:00-65:05].
• Función de evaluación: aproximación del valor de una posición en nodos no terminales; F̃(s) = Σ wi·fi(s) [65:07-66:42].
• Búsqueda iterativa: repetir la búsqueda con mayor profundidad hasta agotar el tiempo disponible [65:07-66:15].
• AlphaZero / Deep Blue / AlphaGo: programas que hicieron historia jugando ajedrez y Go [03:53-06:12].
• Poda hacia delante (forward pruning): podar ramas que parecen malas antes de evaluarlas (p. ej. quedarse con los n mejores movimientos).
• Tabla de finales (lookup): posiciones precalculadas de finales para no buscarlas en tiempo de juego.
• Expectiminimax: minimax con nodos chance que promedian por probabilidad; para juegos con azar.
• MCTS (Monte Carlo Tree Search): búsqueda guiada por simulaciones aleatorias (rollouts); base de AlphaGo/AlphaZero.

7 Mapa mental textual

• Inteligencia Artificial · Clase 7
  • Juegos con adversarios
    • Tipos: determinista/estocástico, número de jugadores, suma cero, información perfecta
    • Estado del arte: damas (1952/1994/2007), ajedrez (Deep Blue 1997), Go (AlphaGo 2016), AlphaZero (auto-juego, 2017)
    • Definición formal: S, P, A, transición, prueba de meta, utilidad terminal; solución = estrategia S→A
  • Búsqueda con adversarios
    • Valor de un estado (Vs = max V(s′))
    • Árboles de juego (sin control total; suponer lo peor)
    • Algoritmo minimax
      • MAX maximiza, MIN minimiza; turnos; árbol
      • Completo y óptimo; O(b^m) tiempo, O(b·m) espacio
      • Generalización a más jugadores (despachador)
    • Podado alfa-beta
      • Alfa (mejor de MAX) y beta (mejor de MIN)
      • Poda sin efecto en la raíz; O(b^(m/2)); el orden importa
    • Limitantes en recursos
      • Profundidad definida
      • Función de evaluación (heurística): F̃(s) = Σ wi·fi(s)
      • Búsqueda iterativa (algoritmo siempre listo)
  • Siguiente tema: Incertidumbre